import java.util.Random;
import util.PrintUtils;

public class Sort {

    public static void main(String[] args) {
//        MinDui model = new MinDui(new int[] {4, 2,11, 4, 1, 5});
//        Random random = new Random();
//        for (int i = 0; i < 20; i++) {
//            model.add(random.nextInt(100));
//            int flag = random.nextInt(2);
//            if (flag % 2 == 0) {
////                System.out.println(model.remove());
//            }
//        }
//        model.print();
        int[] ints = {4, 2, 11, 4, 1, 5};
        quickSort(ints, 0, ints.length - 1);
        PrintUtils.arrayInt(ints);
        //        System.out.println(random.nextInt(100));
    }

    private static void quickSort(int[] source, int i, int j) {
        if (i >= j || i < 0 || j > source.length) {
            return;
        }
        int l = i, r = j;
        while (i < j) {
            while (i < j && source[i] < source[j]) {
                j--;
            }
            swap(source, i, j);
            while (i < j && source[i] <= source[j]) {
                i++;
            }
            swap(source, i, j);
        }
        quickSort(source, l , i - 1);
        quickSort(source, i + 1 , r);
    }

    private static void swap(int[] source, int i, int j) {
        int temp = source[i];
        source[i] = source[j];
        source[j] = temp;
    }

    static class MinDui {
        private int[] arrays;
        private int size;

        public MinDui(int[] inits) {
            arrays = new int[inits.length*2];
            size = inits.length;
            System.arraycopy(inits, 0, arrays, 0, inits.length);
            init();
        }

        /**
         * 初始化构造堆
         */
        private void init() {
            // 最后一个非叶子节点的下标
            int lastUnLeafIndex = (size - 2) / 2;
            for (int unLeafIndex = lastUnLeafIndex; unLeafIndex >= 0; unLeafIndex--) {
                down(unLeafIndex);
            }
        }

        /**
         * 上浮
         * @param index
         */
        private void up(int index) {
            if (index <= 0) {
                return;
            }
            int child = index, parent = (child - 1) / 2;
            int valueChild = arrays[child];
            while (child > 0 && arrays[parent] > valueChild) {
                arrays[child] = arrays[parent];
                child = parent;
                parent = (child - 1) / 2;
            }
            arrays[child] = valueChild;
        }

        /**
         * 下浮
         * @param index
         */
        private void down(int index) {
            int parent = index;
            int minChild = 2 * parent + 1;
            int valueParent = arrays[parent];
            while (minChild < size) {
                if (minChild + 1 < size && arrays[minChild + 1] < arrays[minChild]) {
                    minChild = minChild + 1;
                }
                if (arrays[minChild] < valueParent) {
                    arrays[parent] = arrays[minChild];
                    parent = minChild;
                    minChild = 2 * parent + 1;
                } else {
                    break;
                }
            }
            arrays[parent] = valueParent;
        }

        /**
         * 扩容
         */
        private synchronized void resize() {
            int[] temp = new int[size << 1];
            System.arraycopy(arrays,0, temp, 0, size);
            arrays = temp;
        }

        /**
         * 添加
         * @param value
         */
        public void add(int value) {
            if (size >= arrays.length) {
                resize();
            }
            arrays[size++] = value;
            up(size - 1);
        }

        /**
         * 移除
         * @return
         */
        public int remove() {
            if (size <= 0 ) {
                System.out.println("堆长度为空");
                return -1;
            }
            int value = this.arrays[0];
            size--;
            if (size > 0) {
                arrays[0] = arrays[size];
                down(0);
            }
            return value;
        }

        /**
         * 打印
         */
        public void print() {
            while (size > 0) {
                System.out.print(remove() + "; ");
            }
            System.out.println();
        }
    }
}
